這題是 977. Squares of a Sorted Array 目的是將已排序的陣列每個元素平方後，按非遞減順序排序回傳。

題目：
給定一個已按照非遞減順序排序的整數陣列 nums，我們需要回傳每個元素平方後並排序的結果。

範例：

輸入: nums = [-4, -1, 0, 3, 10]
輸出: [0, 1, 9, 16, 100]

解題思路

先對每個元素平方後再排序回傳結果，

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = nums[i] * nums[i];
        }

        sort(nums.begin(), nums.end());

        return nums;
    }
};

時間複雜度：O(n lon n)，排序需要 O(n lon n)
空間複雜度：O(1)

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

因為陣列已經是排序好的，但是包含負數，負數平方後會導致整個陣列不是按照排序方式排列，
這邊使用雙指標的方式分別指向頭跟尾，因為頭跟尾平方後一定是之後陣列中比較大的那一側，因為只要比較頭跟尾平方後誰比較大，就誰先放進新陣列裡，

考慮到還有全部都是負數的狀況，例如：[-5,-3,-2,-1]，就不能每次迴圈一次將 left 與 right 兩個放入新陣列中，每次迴圈需要一次放一個結果。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = 0;
        int j = nums.size()-1;
        int k = nums.size()-1;
        vector<int> res(nums.size());
        while (i < j) {
            int left = nums[i] * nums[i];
            int right = nums[j] * nums[j];
            if (left > right) {
                res[k] = left;
                i++;
            } else {
                res[k] = right;
                j--;
            }
            k--;
        }
        if (i == j) // is odd
            res[k] = nums[i] * nums[i];

        return res;
    }
};

後來發現可以再簡化，將 i == j 也放入迴圈裡，

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = 0;
        int j = nums.size()-1;
        int k = nums.size()-1;
        vector<int> res(nums.size());
        while (i <= j) {
            int left = nums[i] * nums[i];
            int right = nums[j] * nums[j];
            if (left > right) {
                res[k] = left;
                i++;
            } else {
                res[k] = right;
                j--;
            }
            k--;
        }

        return res;
    }
};

時間複雜度：O(n)，只需要遍歷一次陣列。
空間複雜度：O(n)，需要新陣列來儲存結果。

參考：
#977. Squares of a Sorted Array